﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.笔试
{
    //此题按照寻找数组中第k大的数来做
    //使用大顶堆，调整k次即可
    class SOl
    {
        public int FindKthLargest(int[] nums,int k)
        {

            MakeBigHeap(nums);
            int res = 0;
            for (int i = 1; i <= k; i++)
            {
                res = nums[0];
                MySwap(nums, 0, nums.Length - i);
                AdjustHeap(nums, 0, nums.Length - i);


            }
            return res;

        }

        public void MakeBigHeap(int[] nums)
        {

            for (int i = nums.Length / 2; i >= 0; i--)
            {

                AdjustHeap(nums, i, nums.Length);
            }

        }
        public void AdjustHeap(int[] nums,int i, int len)
        {


            if (i >= len)
            {
                return;
            }
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int bigger = i;
            if (left<len&&nums[left] > nums[bigger])
            {
                bigger = left;

            }
            if (right < len && nums[right] > nums[bigger])
            {
                bigger = right;

            }
            if (i == bigger)
            {
                return;
            }
            else
            {
                MySwap(nums, i, bigger);
                AdjustHeap(nums, bigger, len);
            }



        }

        public void MySwap(int[] nums, int i, int j)
        {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;

        }
    }



    class Program
    {

        static void Main1(string[] args)
        {


            int[] nums = [3, 2, 1, 5, 6, 4];
            int k = 2;
            SOl sOl = new SOl();
        int res=    sOl.FindKthLargest(nums, k);
            Console.WriteLine(res);


        }
    }
}
